package sjjg.tree;

public class MaxPriorityQueue<T extends Comparable> {
    private T[] maxQueue;
    private int N;
    MaxPriorityQueue(int capacity){
        maxQueue=(T[])new Comparable[capacity+1];
        N=0;
    }
    public boolean less(int index1,int index2){
        return maxQueue[index1].compareTo(maxQueue[index2])<0;
    }
    public void exchange(int index1,int index2){
        T temp;
        temp=maxQueue[index1];
        maxQueue[index1]=maxQueue[index2];
        maxQueue[index2]=temp;
    }
    public T delMax(){
        exchange(1,N);
        N--;
        sink(1);
        return maxQueue[N+1];
    }
    public void insert(T t){
        maxQueue[++N]=t;
        swim(N);
    }
    public void swim(int k){
        while (k>1){
            if(less(k/2,k)){
                exchange(k/2,k);
            }else {
                break;
            }
            k=k/2;
        }
    }
    public void sink(int k){
          int max=0;
          while (2*k<=N){
                if(2*k+1<=N){
                    if(less(2*k,2*k+1)){
                        max=2*k+1;
                    }else {
                        max=2*k;
                    }
                }else {
                    max=2*k;
                }
                if(less(max,k)){
                    break;
                }
                exchange(k,max);
                k=max;
          }
    }
    public int size(){
        return N;
    }
    public boolean isEmpty(){
        return N==0;
    }

    public static void main(String[] args) {
        MaxPriorityQueue<String> maxPriorityQueue = new MaxPriorityQueue<>(10);
        maxPriorityQueue.insert("A");
        maxPriorityQueue.insert("B");
        maxPriorityQueue.insert("C");
        maxPriorityQueue.insert("D");
        maxPriorityQueue.insert("E");
        maxPriorityQueue.insert("F");
        maxPriorityQueue.insert("G");
        maxPriorityQueue.insert("H");
        maxPriorityQueue.insert("I");
        while (!maxPriorityQueue.isEmpty()){
            String integer = maxPriorityQueue.delMax();
            System.out.println(maxPriorityQueue.size()+1+"外->"+integer.hashCode());

        }
        System.out.println("I".hashCode());
    }
}
